using System;
using System.Collections.Generic;
using System.Text;

namespace CddSharp
{
    public class BitArray : IEnumerable<int>
    {

        protected static byte[] sizes =
        {
        0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
        1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
        1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
        2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
        1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
        2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
        2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
        3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
        };

        protected int initSize = -1;
        protected byte[] data = null;

        public BitArray(int size)
        {
            initSize = size;
            data = new byte[((initSize & 7) == 0) ? initSize >> 3 : (initSize >> 3) + 1];

            //Core.Log("Set init, size: {0}, data: {1}", _initSize, _data.Length);
        }

        public void Clear()
        {
            data.Initialize();
        }

        public void CopyTo(BitArray newset)
        {
            newset.initSize = this.initSize;
            newset.data = new byte[this.data.Length];
            data.CopyTo(newset.data, 0);
        }

        public BitArray Copy()
        {
            BitArray newset = new BitArray(this.initSize);
            data.CopyTo(newset.data, 0);

            return newset;
        }

        public void SetAll(bool value)
        {
            if (value)
                for (int i = 0; i < data.Length; i++)
                    data[i] = 0xFF;
            else
                data.Initialize();
        }

        public void Set(int item, bool value)
        {
            if (item == 0)
            {
                Console.Write(".");
            }

            if (value)
                Add(item);
            else
                Remove(item);
        }

        public void Add(int item)
        {
            item--;
            byte x = (byte)(0x01 << (item & 7));
            data[item >> 3] |= x;
        }

        public void Remove(int item)
        {
            item--;
            byte x = (byte)(0x01 << (item & 7));
            data[item >> 3] = (byte)((data[item >> 3] | x) ^ x);
        }

        public bool Get(int item)
        {
            item--;

            byte x = (byte)(0x01 << (item & 7));
            return (data[item >> 3] & x) != 0;
        }

        public BitArray And(BitArray otherset)
        {
            //int minsize = otherset.initSize < this.initSize ? otherset._initSize : this.initSize;

            BitArray newset = new BitArray(initSize);

            for (int i = 0; i < newset.data.Length; i++)
                newset.data[i] = (byte)(this.data[i] & otherset.data[i]);

            return newset;
        }

        public BitArray Or(BitArray otherset)
        {
            /*int maxsize = otherset._initSize > this._initSize ? otherset._initSize : this._initSize;

            BitArray newset = new BitArray(maxsize - 1);

            if (this._data.Length < otherset._data.Length)
            {
                for (int i = 0; i < this._data.Length; i ++ )
                    newset._data[i] = (byte)(this._data[i] | otherset._data[i]);
                for (int i = this._data.Length; i < otherset._data.Length; i ++)
                    newset._data[i] = otherset._data[i];
            }
            else
            {
                for (int i = 0; i < otherset._data.Length; i++)
                    newset._data[i] = (byte)(this._data[i] | otherset._data[i]);
                for (int i = otherset._data.Length; i < this._data.Length; i++)
                    newset._data[i] = otherset._data[i];
            }*/

            //int maxsize = otherset._initSize > this.initSize ? otherset._initSize : this.initSize;
            //int minlen = otherset._data.Length < this.data.Length ? otherset._data.Length : this.data.Length;

            BitArray newset = new BitArray(initSize);

            for (int i = 0; i < data.Length; i++)
                newset.data[i] = (byte)(this.data[i] | otherset.data[i]);

            return newset;
        }

        public BitArray Difference(BitArray otherset)
        {   // this \ otherset

            //int minsize = otherset._initSize < this.initSize ? otherset._initSize : this.initSize;

            BitArray newset = new BitArray(initSize);

            for (int i = 0; i < newset.data.Length; i++)
                newset.data[i] = (byte)(this.data[i] & (~otherset.data[i]));

            return newset;
        }

        public BitArray Not()
        {
            BitArray newset = new BitArray(this.initSize);

            for (int i = 0; i < this.data.Length; i++)
                newset.data[i] = (byte)(~this.data[i]);

            newset.ResetLastBits();

            return newset;
        }

        public bool IsSubsetOf(BitArray otherset)
        {
            //ResetLastBits();    // in case of inconsistency

            int minlen = otherset.data.Length < this.data.Length ? otherset.data.Length : this.data.Length;

            // this doesn't check the remaining bytes in the larger array!
            for (int i = 0; i < minlen; i++)
                if ((this.data[i] | otherset.data[i]) != otherset.data[i])
                    return false;

            return true;
        }

        public int Count
        {
            get
            {
                //ResetLastBits();

                int count = 0;
                for (int i = 0; i < this.data.Length; i++)
                    count += sizes[this.data[i]];

                return count;
            }
        }

        protected void ResetLastBits()
        {
            

            // setting last bits to zero
            int l = this.data.Length << 3 - initSize;            
            if (l > 0)
            {
                byte x = (byte)(0x01 << (8 - l));
                for (int i = l; l > 0; l--)
                {
                    this.data[this.data.Length - 1] = (byte)((this.data[this.data.Length - 1] | x) ^ x);
                    x = (byte)(x << 1);
                }
            }
            // first (0th bit)
            //this._data[0] = (byte)((this._data[0] | 1) ^ 1);
        }

        public void Write(System.IO.TextWriter writer)
        {
            //for (int i = 0; i < _data.Length; i ++)
            //    writer.Write("{0,2:X}", _data[i]);

            for (int i = 1; i < initSize; i++)
                writer.Write(Get(i) ? "1" : "0");

            writer.WriteLine();
        }

        #region IEnumerable<int> Members

        public IEnumerator<int> GetEnumerator()
        {
            int counter = 0;
            while (counter < initSize)
            {
                while (counter < initSize && !this.Get(counter)) counter++;

                if (counter < initSize)
                    yield return counter++;
            }
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            int counter = 0;
            while (counter < initSize)
            {
                while (!this.Get(counter) && counter < initSize) counter++;

                if (counter < initSize)
                    yield return counter++;
            }
        }

        #endregion
    }
}